package org.myy.learn.aaa.b_双指针;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@Slf4j
public class 三数之和 {

    //问题：num[i]+num[j]+num[k]==0 且 num[i] != num[j] != num[k]
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i=0; i<n; i++){              //以i为起点
            if (nums[i] > 0){break;}          //排序的作用一就在这里
            if (i>0 && nums[i] == nums[i-1]){break;} //排除重复数据[重复绝对开始于第二位] >> 排序的作用三就在这里
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            while (left < right){             //排序的作用二就在这里[向中间走]
                int sum = nums[left] + nums[right];
                if (sum == target){           //二分查找
                    list.add(List.of(nums[i], nums[left], nums[right]));//入列
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left-1]){left++;}    //排除重复数据
                    while (left < right && nums[right] == nums[right+1]){right--;} //排除重复数据
                } else if (sum < target){
                    left++;
                } else {
                    right--;
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        List<List<Integer>> threeSum = threeSum(nums);
        log.info("执行结束，threeSum={}", threeSum);

    }

}
